package leetcode_day._2021._202111;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/18 13:09
 * 二叉树的坡度
 * 给定一个二叉树，计算 整个树 的坡度 。一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。
 * 如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。整个树 的坡度就是其所有节点的坡度之和。
 * 算法：二叉树 + 递归
 */
public class _18_563 {

    int ans;
    public int findTilt(TreeNode root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode root) {
        if (root == null) return 0;
        int l = dfs(root.left), r = dfs(root.right);
        ans += Math.abs(l - r);
        return l + r + root.val;
    }

}
